package com.huangyi;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //衣橱整理
        class Solution {
            int[] dx = {1, 0};   // 向下、向右
            int[] dy = {0, 1};
            int m, n, cnt;
            boolean[][] vis;
            int result;

            public int wardrobeFinishing(int _m, int _n, int _cnt) {
                m = _m;
                n = _n;
                cnt = _cnt;
                vis = new boolean[m][n];
                result = 0;

                dfs(0, 0);
                return result;
            }

            public void dfs(int si, int sj) {
                vis[si][sj] = true;
                result++;  // 计数当前格子

                for (int i = 0; i < 2; i++) {
                    int x = si + dx[i];
                    int y = sj + dy[i];

                    // 边界检查 + 访问检查 + 数位和检查
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                        int sum = get(x) + get(y);
                        if (sum <= cnt) {
                            dfs(x, y);  // 递归访问
                        }
                    }
                }
            }

            // 计算数字各位数字之和
            public int get(int num) {
                int sum = 0;
                while (num > 0) {
                    sum += num % 10;  // 取个位
                    num = num / 10;   // 去掉个位
                }
                return sum;
            }
        }


        //斐波那契数
        class Solution2 {
            int[] memo;
            public int fib(int n) {
                memo = new int[31];
                Arrays.fill(memo, -1);
                return dfs(n);
            }

            public int dfs(int n){
                if(n == 0 || n ==1) return n;
                if(memo[n] != -1){
                    return memo[n];
                }

                memo[n] = dfs(n-1) + dfs(n-2);
                return memo[n];
            }
        }
    }
}